%\course{ICE-EM/AMSI Summer School {\it Cryptography}}
%\heading{Summer}{RSA Cryptosystems}{2007}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:find_large_prime_compute_inverse_exponentiation}}]
The function call \verb!random_prime($2^{100}$)! returns a random 
prime of up to 100 bits.  Suppose that the primes 
$$
\begin{array}{l} 
p = 1172991670841347272989353064539, \\
q = 300997517969507552061104346547,
\end{array}
$$
are found with this function, and set $e = 5$.  We want to build the 
inverse exponent $d$ such that 
$ed \equiv 1 \bmod (p-1)$ and 
$ed \equiv 1 \bmod (q-1)$.  Note first that $\gcd(e,p-1)=1$ and 
$\gcd(e,q-1)=1$, so that such a $d$ must exist.  We first compute 
each of $d \bmod (p-1)$ and $d \bmod (q-1)$.
%\input{code/solution11.1.m}
\input{code/solution11.1.sage}
The value of $d$ can now be computed modulo the value $\lcm(p-1,q-1)$
--- this is sufficient to determine the inverse, rather than the larger 
value of the product $(p-1)(q-1)$.  

We would like to compute the value of $d$, but the Sage function
{\tt crt} complains that the moduli $p-1$ and $q-1$ have a common factor.
%\input{code/solution11.2.m}
\input{code/solution11.2.sage}
We can divide $q-1$ by 6 to remove the common factor, and so compute 
the Chinese remainder lifting as follows.  Note first that the system
is consistent --- $d_1$ and $d_2$ are the same modulo $6$ since they 
are both inverses to $e \bmod 6$.
%\input{code/solution11.3.m}
\input{code/solution11.3.sage}
Since $(q-1)/6$ is not divisible by 2 or 3, we can proceed with the 
Chinese remainder lifting with $p-1$ and $(q-1)/6$.
%\input{code/solution11.4.m}
\input{code/solution11.4.sage}
Alternatively we could have computed the inverse exponent $d$ in 
one step by 
%\input{code/solution11.5.m}
\input{code/solution11.5.sage} 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:use_exponents_verify_identities}}]
Now we can verify that $e$ and $d$ are inverses modulo $p-1$ and 
modulo $q-1$, and, moreover, that they determine inverse exponential 
maps modulo the RSA modulus $n = pq$. 
%\input{code/solution11.6.m}
\input{code/solution11.6.sage}

We use the RSA cryptosystem in Sage as follows.  First begin with 
encoding ASCII text numerically:
%\input{code/tutorial11.1.m}
\input{code/tutorial11.1.sage}
Note that, as with LFSR cryptosystems, RSA encoding uses the 
information-preserving ASCII bit encoding, and encoding and decoding 
are true inverses.  {\bf Caution:} we note that printing ``decoded'' 
ciphertext might render an terminal nonfunctional, since the resulting 
ASCII text might contain escape characters which reset the terminal 
display.

\noindent
To encipher, first we must create a key pair:
%\input{code/tutorial11.2.m}
\input{code/tutorial11.2.sage}
This returns a pair of inverse keys $\tK$ and $\tL$.  We will consider 
$\tK$ to be the public $\tK$ and $\tL$ to be the private key. 

\noindent
{\bf N.B.} The argument to {\tt RSACryptosystem} specifies the number 
of bits in the RSA modulus.  With a value of $128$, the modulus is of 
size $2^{128}$, or about $39$ decimal digits.  Each of the primes is 
of size approximately $20$ decimal digits.  This particular example 
can be easily broken by the factorization:
%\input{code/tutorial11.3.m}
\input{code/tutorial11.3.sage}
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:reproduce_private_key_with_factorization}}]
Given the factorization
\begin{multline*}
86398677368792768067556452456311743331\\ 
  = 6046864213681032211 \cdot 14288178850339607921,
\end{multline*}
we can find the inverse to the exponent 
$$
e = 49338921862830381807760291818994034053.
$$ 
%\input{code/solution11.7.m}
\input{code/solution11.7.sage}
It is now possible to verify as above that $(e,n)$ and $(d,n)$ 
server as inverse RSA keys.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:arbitrary_choice_pubkey_prikey}}]
Provided that $e$ is chosen as a random number in the range 
$$
1 \le e \le \lcm(p-1,q-1),
$$
which has no common factors with $p-1$ or $q-1$, then its inverse 
is a similarly random value in this range.  Therefore after creation,
the decision of which key to publish as the public key, and which 
key to guard as the private key is arbitrary.  

{\bf N.B.} Sometimes a special value, such as $3$, $5$, $17$, $257$, 
or $65537$, is chosen as the public exponent.  These are each of the 
form $2^r+1$, so that the enciphering can be done rapidly using only 
$r$ squarings and one multiplication.  In such a case it is clear 
that no such ``obvious'' value is suitable for the private key, and 
the symmetry of the choice between public and private keys is 
broken. 
\end{proof}

%\course{ICE-EM/AMSI Summer School {\it Cryptography}}
%\heading{Summer}{Diffie--Hellman and Discrete Logarithms}{2007}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:solve_discrete_log_then_solve_Diffie_Hellman_problem}}]
Suppose that the discrete logarithm problem has an efficient 
solution.  Then, given a primitive element $a$ of $\F_p$, for 
every $a^x$ and $a^y$ we could solve for $x = \log_a(a^x)$ and 
for $y = \log_a(a^y)$.  It follows that we could then produce 
the value $a^{xy}$, which solves the Diffie-Hellman problem. 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:Fermat_little_theorem_primitive_element}}]
The statement of the definition of primitive is a formal statement 
equivalent to that which follows.  An element $a$ of $\Z/p\Z$ is 
primitive if and only if 
$$
1,a,a^2,\dots,a^{p-2} 
$$
are all distinct, and therefore enumerate all nonzero elements 
of $\Z/p\Z$.  

\begin{enumerate}
\item 
Fermat's little theorem tells us that the next 
value, $a^{p-1}$ in this list is $1$, and therefore $a^x = 1$
for all $x = r(p-1)$, and indeed, we have run out of nonzero 
elements so must have a repeat at this point.  

Conversely for any nonzero element $a$ there must be some value 
$t$ such that $a^t = 1$, hence $a^{rt}=1$ for all~$r$.  We may 
assume that $t$ divides $p-1$, since if $t' = \gcd(t,p-1)$ then 
there exist $r$ and $s$ such that $t' = rt + s(p-1)$, so
$$
1 = a^{rt}a^{s(p-1)} = a^{rt + s(p-1)} = a^{t'},
$$
and we can replace $t$ by $t'$.  Therefore the maximum length 
of a cycle $1,a,a^2,\dots,a^{t-1}$ divides $p-1$ and is equal l
to $p-1$ exactly when $a$ is primitive.

\item 
For $p = 2^{32}+15$, the factorization of $p-1$ is $2 \cdot 3^2 
\cdot 5\cdot 131 \cdot 364289$.  We need to check that $3^x$ is 
not $1 \bmod p$ for any divisor of $p-1$. 
%\input{code/solution12.1.m}
\input{code/solution12.1.sage}
How does this prove that 3 is a primitive element?

By producing random elements in $\F_p$ and computing discrete 
logarithms with respect to $a$, we find that the time to compute 
discrete logarithms in $\F_p = \Z/p\Z$ is trivial.
%\input{code/solution12.2.m}
\input{code/solution12.2.sage}

\item 
For $p = 2^{32}+61$, the factorization of $p-1$ is $2^2\cdot 1073741839$.
We repeat the same test as in the previous part.
%\input{code/solution12.3.m}
\input{code/solution12.3.sage}
The shows that 2 is a primitive element.  Next we find that, for 
this prime $p$, that the time to compute discrete logarithms in 
$\F_p = \Z/p\Z$ is nontrivial.
%\input{code/solution12.4.m}
\input{code/solution12.4.sage}
\end{enumerate} 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:compare_computation_time_discrete_log}}]
The nontrivial time for the discrete logarithm is due to the large 
prime divisor of $p-1$.  The amount of time required to compute a 
discrete logarithm in $\F_p$ is dependent on the size of the largest 
prime divisor of $p-1$.  The discrete logarithm can be computed 
independently for each prime divisor of $p-1$ --- more correctly for 
prime power divisor --- and the discrete logarithm can be recovered 
by the Chinese remainder theorem, as is the next example.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:pubkey_crypto:verify_factorization}}]
We set up the problem in Sage in the following way.
%\input{code/solution12.5.m}
\input{code/solution12.5.sage}
In this way, $p_1$, $p_2$, $p_3$, $p_4$, $p_5$, and $p_6$ are assigned 
to be the prime divisors of $p-1$ and $n_1$, $n_2$, $n_3$, $n_4$, $n_5$, 
and $n_6$ their cofactors.

Raising both generator $a$ and its power $c$ to the large exponents 
$n_1$, $n_2$, $n_3$, and $n_4$ reduces the solution to the discrete 
logarithm to one modulo $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, and $p_4 = 37$, 
which can be easily solved by enumerating all possibilities.
%\input{code/solution12.6.m}
\input{code/solution12.6.sage}
For the larger primes 
$$
p_5 = 634466267339108669 \hbox{ and } 
p_6 = 3865430919824322067,
$$
we verify the given discrete logarithms.
%\input{code/solution12.7.m}
\input{code/solution12.7.sage}
The discrete logarithm $x$ can be recovered from the discrete 
logarithms $x_i = \log_{a_i}(c_i)$ where $a_i = a^{n_i}$ and 
$c_i = c^{n_i}$ by using the function {\tt crt} to find the 
Chinese remainder lifting. 
%\input{code/solution12.8.m}
\input{code/solution12.8.sage} 
\end{proof}
